from __future__ import print_function
import math

nb_points = 400 
nb_steps = 4 
max_x = 24 # nb rows
max_y = 35 # nb cols
x_width = max (1, max_x / 10)
y_width = max(1, max_y / 10)
x_space = " " * x_width
def distance(point1, point2):
	distx = max(point1.x,point2.x) - min(point1.x,point2.x)
	disty = max(point1.y,point2.y) - min(point1.y,point2.y)
	return math.sqrt(distx*distx+disty*disty)


class Point(object):

	def __init__(self, name, x, y):
		self.name = name
		self.x = x
		self.y = y

	def compute_distance(self, point):
		return distance(self, point) 


class DistanceToPoint(Point):
	
	def __init__(self, my_point, other_point):
		self.my_point = my_point
		self.name = "Distance from " + str(my_point.name) + " to " + str(other_point.name)
		self.x = self.my_point.x
		self.y = self.my_point.y
		self.other_point = other_point
		self.distance_to_other_point = self.compute_distance(self.other_point)
	def get_other_point(self):
		return self.other_point

import random 

def generate_point(id_point, max_x,max_y):
	x = random.randint(0,max_x-1)
	y = random.randint(0,max_y-1)
	return Point(id_point, x, y)

def generate_points(max_points, max_x, max_y):
	if max_x * max_y < max_points:
		raise BaseException("Impossible to generate this set of points within the defined grid")
	points = list()
	while len(points) != max_points: 
		#print("x {0}, y{1}".format(x,y))
		ok = False
		while not ok:
			point = generate_point(len(points), max_x, max_y)
			different = True
			for p in points:
				different = different and  (p.x != point.x or p.y != point.y)
			ok = different
		points.append(point)
	return points

def distance_3_points(A, B, interm):
	return A.compute_distance(interm) + B.compute_distance(interm)

def update_closer(closer_list, ref_point, dist_point):
	dist = DistanceToPoint(ref_point, dist_point)
	for idx,d in enumerate(closer_list):
		if dist.distance_to_other_point < d.distance_to_other_point:
			print("CHANGING")
			closer_list[idx] = dist
			break

class Route(object):
	def __init__(self, start_point, end_point, required_steps):
		self.start_point = start_point
		self.end_point = end_point
		self.current_point = start_point
		self.required_steps = required_steps
		self.waypoints = []

	def current_length(self):
		leng = 0
		if len(self.waypoints) > 0:
			leng = distance(self.start_point,self.waypoints[0])
		for idx in range(1,len(self.waypoints)):
			leng += distance(self.waypoints[idx-1],self.waypoints[idx])
		if len(self.waypoints) == self.required_steps:
			leng + distance(self.waypoints[-1] , self.end_point)
		return leng

	def length(self):
		if len(self.waypoints) != self.required_steps:
			return max_x**2 + max_y**2
		leng = distance(self.start_point,self.waypoints[0])
		for idx in range(1,len(self.waypoints)):
			leng += distance(self.waypoints[idx-1],self.waypoints[idx])
		leng += distance(self.waypoints[-1] , self.end_point)
		return leng
	def add_waypoint(self, point):
		self.waypoints.append(point)
		pass 

	def remove_last_waypoint(self):
		self.waypoints.remove(self.waypoints[-1])

	def print_route(self):
		print("A({0},{1})->".format(self.start_point.x,self.start_point.y),end="")
		for p in self.waypoints:
			print("{0}({1},{2})->".format(p.name, p.x, p.y),end="")
		for miss in range(len(self.waypoints),self.required_steps):
			print("?->",end="")
		print("B({0},{1}) : {2}".format(self.end_point.x,self.end_point.y,self.length()))
		

def launch_dijkstra(start_point, end_point, nb_steps, points):
	route = Route(start_point, end_point, nb_steps)
	best_route = copy.deepcopy(route)
	best_route = tuned_dijkstra(0, nb_steps, points, route, best_route)
	#best_route.print_route()
	return best_route
import copy

def tuned_dijkstra( current_step, max_steps, points, route, best_route):
#	if current_step == max_steps:
#		return best_route
	my_base_route = copy.deepcopy(route)
	#my_best_route = copy.deepcopy(best_route)
	my_best_route = best_route
	if my_base_route.current_length() > my_best_route.length():
		return my_best_route
	new_points = copy.copy(points)
	#print("{0}".format(current_step))
	for p in points:
		#route.print_route()
		route.add_waypoint(p)
		if current_step != max_steps - 1:
			new_points.remove(p)
			route = tuned_dijkstra( current_step + 1, max_steps, new_points, route, my_best_route)
			new_points.append(p)
		else:
			#route.print_route()
			pass
		if route.length() < my_best_route.length():
			my_best_route = copy.deepcopy(route)
			#my_best_route.print_route()
		route = copy.deepcopy(my_base_route)	
	#print("Finishing Dijkstra with best_route @ step {0}".format(current_step))
	#my_best_route.print_route()
	return my_best_route

def add_display_point(point, letter, txt_points):
	#print("{0} {1}".format(len(txt_points),len(txt_points[0])))
	#print("{0} {1}".format(point.x,point.y))
	row = int(point.x)
	col = int(point.y)
	if txt_points[row][col] != " ":
		print("{0} overwritten by {1}".format(txt_points[row][col], letter))
	if txt_points[row][col] != "A" and txt_points[row][col]!= "B":
		txt_points[row][col] = letter

def display_x_axis():
	print("{0:4}".format(""),end="")
	for col in range(max_y):
		print("{0:4}".format(col),end="")
	print()


def display_points( A, B, omega, points, max_x, max_y):
	txt_points = []
	for row in range(max_x):
		txt_points.append([" "] * max_y)
	add_display_point(A,"A",txt_points)
	add_display_point(B,"B",txt_points)
	add_display_point(omega,"O",txt_points)
	for p in points:
		add_display_point(p, p.name, txt_points)
	display_x_axis()	
	for row in range(max_x):
		print("{0:4} ".format(row),end="")
		for col in range(max_y):
			print("{0:4}".format(txt_points[row][col]),end="")
		print()
	display_x_axis()

points = generate_points(nb_points, max_x, max_y)
#print("{0}".format(points))

A = generate_point("A", max_x, max_y)
B = generate_point("B", max_x, max_y)
omega = Point( "omega", (A.x+B.x)/2.0 , (A.y+B.y)/2.0 )
display_points(A, B, omega, points, max_x, max_y)
print("Name = {0}\nx,y = {1},{2}".format(A.name, A.x, A.y))
print("Name = {0}\nx,y = {1},{2}".format(B.name, B.x, B.y))
print("Name = {0}\nx,y = {1},{2}".format(omega.name, omega.x, omega.y))

print("Dist A,B : {0}".format(A.compute_distance(B)))
print("{0} and dist {1}".format(omega.name,distance_3_points(A,B,omega)))

closer_to_A = [ DistanceToPoint(A, p) for p in points[0:nb_steps]  ]
closer_to_B = [DistanceToPoint(B, p) for p in points[0:nb_steps] ]
closer_to_omega = [DistanceToPoint(omega, p) for p in points[0:nb_steps] ]

for a in closer_to_A: print("{0}".format(a.name))
for b in closer_to_B: print("{0}".format(b.name))
for o in closer_to_omega: print("{0}".format(o.name))

for p in points[nb_steps:]:
	#print("update A")
	update_closer(closer_to_A, A, p)
	#print("update B")
	update_closer(closer_to_B, B, p)
	#print("update Omega")
	update_closer(closer_to_omega, omega, p)
	pass
'''
for a in closer_to_A: print("{0}".format(a.name))
for b in closer_to_B: print("{0}".format(b.name))
for o in closer_to_omega: print("{0}".format(o.name))
'''
def discard_too_far_away_points(A, B, points, best_length):
	points_to_remove = []
	for p in points:
		dist = distance_3_points(A,B,p)
		#print("{0} and {1}".format(dist, best_length))
		if distance_3_points(A,B,p) > best_length:
			points_to_remove.append(p)
	print("Removing {0} too far away points".format(len(points_to_remove)))
	for p in points_to_remove:
		points.remove(p)

closest_points = [] + closer_to_A + closer_to_B + closer_to_omega
closer_points = list(set([ p.get_other_point() for p in closest_points ]))
display_points(A, B, omega, points, max_x, max_y)
print("Executing First heuristic djikstra on {0} points".format(len(closer_points)))
best_route = launch_dijkstra(A,B,nb_steps,closer_points)
display_points(A, B, omega, points, max_x, max_y)

print("First set of closest points selected : ")
for o in closer_points: print("{0} ".format(o.name),end='')
print()
print("First route found with first set of closest points: ",end='')
best_route.print_route()
'''
discard_too_far_away_points(A,B,points, 1.5 * best_route.length())
print("Interm set of closest points selected : ")
for o in points: print("{0} ".format(o.name),end='')
print()
print("Interm route found with Interm set of closest points: ",end='')
interm_best_route = launch_dijkstra(A,B,nb_steps,points)
interm_best_route.print_route()
'''
discard_too_far_away_points(A,B,points, best_route.length())
print("Final set of closest points selected : ")
for o in points: print("{0} ".format(o.name),end='')
print()
print("Final route found with final set of closest points: ",end='')
last_best_route = launch_dijkstra(A,B,nb_steps,points)
last_best_route.print_route()

import os
'''
if last_best_route.length() != interm_best_route.length():
	os.sys.exit(1000)
'''
if last_best_route.length() > best_route.length():
	print("Error: last_best_route > best_route, which means the theory behind the approximation of the solution is wrong")
	os.sys.exit(2000)
os.sys.exit(0)
